JOI 14本選 A JOI紋章(難易度6)
この問題は差分更新をすることによって解くことができる.
まず, あらかじめ古いJOI旗に含まれるJOI紋章の数を前計算しておく.
JOI旗の1箇所を変更したとき, 変更があるのはそのマスが含まれる
$ 2 * 2
の正方形で, これらについて元からJOI紋章だったか, 新しくJOI紋章になったかは定数時間で更新できる. よってこの問題を
$ O(MN)
で解くことができた.
実装例:
https://atcoder.jp/contests/joi2014ho/submissions/15569204